package com.chengzhi.structure;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: 堆
 * @author: ruanchengzhi
 * @create: 2020-03-16 15:49
 **/
public class MaxHeap<E extends Comparable<E>> {

    private List<E> data;

    public MaxHeap(int length) {
        this.data = new ArrayList<>(length);
    }

    //heapify:讲任意数组整理成堆的形状 O(n)
    public MaxHeap(List<E> data) {
        this.data = data;
        //从最后一个非叶子节点开始，逐个siftDown
        for (int i = parentIndex(data.size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public void add(E e) {
        data.add(e);
        siftUp(data.size() - 1);
    }

    public E deleteMax() {
        if (data.size() == 0) {
            throw new IllegalArgumentException("data is empty");
        }
        E e = data.get(0);
        data.add(0, data.get(data.size() - 1));
        data.remove(0);
        siftDown(0);
        return e;
    }

    private void siftUp(int index) {
        while (index > 0 && data.get(index).compareTo(data.get(parentIndex(index))) > 0) {
            swap(index, parentIndex(index));
            index = parentIndex(index);
        }
    }

    private void swap(int index, int parentIndex) {
        data.add(index, data.get(parentIndex));
        data.add(parentIndex, data.get(index));
    }

    private void siftDown(int index) {
        while (leftChildIndex(index) < data.size()) {
            int j = leftChildIndex(index);
            if (j + 1 < data.size() &&
                    data.get(j + 1).compareTo(data.get(j)) > 0) {
                j++;
            }
            if (data.get(index).compareTo(data.get(j)) >= 0) {
                break;
            }
            swap(index, j);
            index = j;
        }

    }

    public boolean contains(E e) {
        return data.contains(e);
    }

    private int parentIndex(int index) {
        return (index - 1) / 2;
    }

    private int leftChildIndex(int index) {
        return index * 2 + 1;
    }

    private int rightChildIndex(int index) {
        return index * 2 + 2;
    }
}
